package com.yanceysong.codetop.s71_s80;


public class S80_Mid_695_岛屿的最大面积 {
    /**
     * .S80_Mid_695_岛屿的最大面积
     * .<p>
     * .<a href="https://leetcode.cn/problems/max-area-of-island/">https://leetcode.cn/problems/max-area-of-island/</a>
     * .<p>
     * .给你一个大小为 m x n 的二进制矩阵 grid。岛屿是由一些相邻的 1（代表土地）构成的组合，
     * .相邻要求两个 1 必须在水平或者竖直的四个方向上相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。
     * .<p>
     * .岛屿的面积是岛上值为 1 的单元格的数目。
     * .计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0。
     * .<p>
     * .示例 1:
     * .<p>
     * .输入：grid = [[0 , 0 , 1 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 , 0],
     * .             [0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 1 , 1 , 0 , 0 , 0],
     * .             [0 , 1 , 1 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0],
     * .             [0 , 1 , 0 , 0 , 1 , 1 , 0 , 0 , 1 , 0 , 1 , 0 , 0],
     * .             [0 , 1 , 0 , 0 , 1 , 1 , 0 , 0 , 1 , 1 , 1 , 0 , 0],
     * .             [0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0],
     * .             [0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 1 , 1 , 0 , 0 , 0],
     * .             [0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 1 , 0 , 0 , 0 , 0]]
     * .输出：6
     * .解释：答案不应该是 11，而是 6。
     * .<p>
     * .示例 2:
     * .<p>
     * .输入：grid = [[0 , 0 , 0 , 0 , 0 , 0 , 0 , 0]]
     * .输出：0
     * .<p>
     * .提示：
     * .<p>
     * .m == grid.length
     * .n == grid[i].length
     * .1 <= m, n <= 50
     * .grid[i][j] 为 0 或 1
     * .<p>
     * .核心标签：
     * .- 深度优先搜索（DFS）
     * .- 矩阵遍历
     * .- Flood Fill 算法
     * .- 岛屿问题/连通分量
     * .<p>
     * .类似题目：
     * .- S14_Mid_200_岛屿数量
     * .- 463. 岛屿的周长
     * .- 827. 最大人工岛
     * .<p>
     * .算法原理：深度优先搜索（DFS）+ Flood Fill
     * .<p>
     * .核心思想：
     * .1. 遍历整个二维网格的每一个格子
     * .2. 当遇到陆地（值为1）时，从该点开始进行深度优先搜索（DFS）
     * .3. 在DFS过程中，统计连通的陆地数量（即当前岛屿的面积）
     * .4. 将访问过的陆地标记为海洋（值改为0），避免重复访问
     * .5. 记录并更新遇到的最大岛屿面积
     * .<p>
     * .为什么使用DFS？
     * .- DFS能够递归地探索一个岛屿的所有连通陆地
     * .- 通过上下左右四个方向的递归，可以完整遍历整个岛屿
     * .- 类似于"洪水填充"（Flood Fill）算法，从一个点扩散到整个连通区域
     * .<p>
     * .图解示例：
     * .<p>
     * .示例网格（4x4）：
     * .    0   1   2   3
     * .  +---+---+---+---+
     * .0 | 0 | 1 | 0 | 0 |
     * .  +---+---+---+---+
     * .1 | 1 | 1 | 1 | 0 |
     * .  +---+---+---+---+
     * .2 | 0 | 1 | 0 | 0 |
     * .  +---+---+---+---+
     * .3 | 0 | 0 | 0 | 1 |
     * .  +---+---+---+---+
     * .<p>
     * .岛屿分析：
     * .- 岛屿1（十字形）：包含 (0 , 1), (1 , 0), (1 , 1), (1,2), (2,1)，面积 = 5
     * .- 岛屿2（单独）：包含 (3,3)，面积 = 1
     * .- 最大面积 = 5
     * .<p>
     * .DFS执行过程（从 grid[0][1] = 1 开始）：
     * .<pre>
     * .初始状态：发现 grid[0][1] = 1
     * .    0   1   2   3
     * .  +---+---+---+---+
     * .0 | 0 |[1]| 0 | 0 |  ← 起点
     * .  +---+---+---+---+
     * .1 | 1 | 1 | 1 | 0 |
     * .  +---+---+---+---+
     * .2 | 0 | 1 | 0 | 0 |
     * .  +---+---+---+---+
     * .3 | 0 | 0 | 0 | 1 |
     * .  +---+---+---+---+
     *
     * .步骤1：访问 (0 , 1)，标记为0，面积 = 1
     * .    0   1   2   3
     * .  +---+---+---+---+
     * .0 | 0 | 0 | 0 | 0 |
     * .  +---+---+---+---+
     * .1 | 1 | 1 | 1 | 0 |
     * .  +---+---+---+---+
     * .2 | 0 | 1 | 0 | 0 |
     * .  +---+---+---+---+
     * .3 | 0 | 0 | 0 | 1 |
     * .  +---+---+---+---+
     *
     * .步骤2：向下探索 (1 , 1)，标记为0，面积 = 2
     * .    0   1   2   3
     * .  +---+---+---+---+
     * .0 | 0 | 0 | 0 | 0 |
     * .  +---+---+---+---+
     * .1 | 1 | 0 | 1 | 0 |
     * .  +---+---+---+---+
     * .2 | 0 | 1 | 0 | 0 |
     * .  +---+---+---+---+
     * .3 | 0 | 0 | 0 | 1 |
     * .  +---+---+---+---+
     *
     * .步骤3：从 (1 , 1) 向左探索 (1 , 0)，标记为0，面积 = 3
     * .步骤4：从 (1 , 1) 向右探索 (1,2)，标记为0，面积 = 4
     * .步骤5：从 (1 , 1) 向下探索 (2,1)，标记为0，面积 = 5
     *
     * .最终状态：整个岛屿被标记，返回面积 = 5
     * .    0   1   2   3
     * .  +---+---+---+---+
     * .0 | 0 | 0 | 0 | 0 |
     * .  +---+---+---+---+
     * .1 | 0 | 0 | 0 | 0 |
     * .  +---+---+---+---+
     * .2 | 0 | 0 | 0 | 0 |
     * .  +---+---+---+---+
     * .3 | 0 | 0 | 0 | 1 |
     * .  +---+---+---+---+
     * .</pre>
     * .<p>
     * .关键洞察：
     * .1. 为什么要将访问过的陆地标记为0？
     * .   - 避免重复计算同一个岛屿的面积
     * .   - 空间优化：不需要额外的 visited 数组
     * .<p>
     * .2. 边界条件处理：
     * .   - 当 i < 0 或 i >= m：越过上下边界
     * .   - 当 j < 0 或 j >= n：越过左右边界
     * .   - 当 grid[i][j] == 0：遇到海洋或已访问的陆地
     * .<p>
     * .3. DFS的递归顺序（上下左右）：
     * .   - dfs(i+1, j)  向下
     * .   - dfs(i-1, j)  向上
     * .   - dfs(i, j+1)  向右
     * .   - dfs(i, j-1)  向左
     * .   顺序可以任意调整，不影响结果
     * .<p>
     * .时间复杂度：O(m * .n)
     * .- 外层双重循环遍历所有格子：O(m * .n)
     * .- 每个格子最多被访问一次（访问后标记为0）
     * .- 总时间复杂度：O(m * .n)
     * .<p>
     * .空间复杂度：O(m * .n)
     * .- 递归调用栈的深度最坏情况下为 O(m * .n)
     * .- 最坏情况：整个网格都是陆地，DFS会递归遍历所有格子
     * .- 没有使用额外的辅助数据结构（原地修改）
     */
    public int maxAreaOfIsland(int[][] grid) {
        // 记录遇到的最大岛屿面积
        int maxArea = 0;

        // 遍历整个二维网格的每一个格子
        // row 表示行索引，column 表示列索引
        for (int row = 0; row < grid.length; row++) {
            for (int column = 0; column < grid[0].length; column++) {
                // 当遇到陆地（值为1）时，启动DFS计算当前岛屿面积
                if (grid[row][column] == 1) {
                    // 计算当前岛屿面积，并更新最大值
                    int currentArea = dfs(grid, row, column);
                    maxArea = Math.max(maxArea, currentArea);
                }
            }
        }

        // 返回最大岛屿面积
        return maxArea;
    }

    /**
     * .深度优先搜索：计算从当前位置开始的岛屿面积
     * <p>
     * .@param grid 二维网格
     * .@param row  当前行索引
     * .@param column  当前列索引
     * .@return 从当前位置开始的连通岛屿面积
     */
    private int dfs(int[][] grid, int row, int column) {
        // 边界条件检查：
        // 1. 越界：行或列超出网格范围
        // 2. 遇到海洋：grid[row][column] == 0（可能是本来的海洋或已访问过的陆地）
        if (row < 0 || row >= grid.length ||
            column < 0 || column >= grid[0].length ||
            grid[row][column] == 0) {
            // 返回 0 表示该位置不贡献面积
            return 0;
        }

        // 当前格子是陆地，面积贡献为 1
        int currentIslandArea = 1;

        // 将当前陆地标记为海洋（值改为0），避免重复访问
        // 这是一种原地修改的优化方法，不需要额外的 visited 数组
        grid[row][column] = 0;

        // 向四个方向递归搜索，累加相邻陆地的面积
        // 向下搜索：行索引 +1
        currentIslandArea += dfs(grid, row + 1, column);
        // 向上搜索：行索引 -1
        currentIslandArea += dfs(grid, row - 1, column);
        // 向右搜索：列索引 +1
        currentIslandArea += dfs(grid, row, column + 1);
        // 向左搜索：列索引 -1
        currentIslandArea += dfs(grid, row, column - 1);

        // 返回总面积：当前格子(1) + 四个方向的面积之和
        return currentIslandArea;
    }

    /**
     * .测试入口：构造各种场景的网格并验证结果
     */
    public static void main(String[] args) {
        S80_Mid_695_岛屿的最大面积 solution = new S80_Mid_695_岛屿的最大面积();

        System.out.println("=== 岛屿的最大面积测试开始 ===");

        // 测试1：十字形岛屿 + 单独小岛
        System.out.println("\n--- 测试1: 十字形岛屿 + 单独小岛 ---");
        testCrossShapeIsland(solution);

        // 测试2：全为海洋
        System.out.println("\n--- 测试2: 全为海洋 ---");
        testAllWater(solution);

        // 测试3：全为陆地
        System.out.println("\n--- 测试3: 全为陆地(3x3) ---");
        testAllLand(solution);

        // 测试4：多个独立小岛
        System.out.println("\n--- 测试4: 多个独立小岛 ---");
        testMultipleIslands(solution);

        // 测试5：LeetCode 官方示例 1
        System.out.println("\n--- 测试5: LeetCode 官方示例 1 ---");
        testLeetCodeExample1(solution);

        // 测试6：单个陆地格子
        System.out.println("\n--- 测试6: 单个陆地格子 ---");
        testSingleLand(solution);

        // 测试7：L形岛屿
        System.out.println("\n--- 测试7: L形岛屿 ---");
        testLShapeIsland(solution);

        // 测试8：对角线不相连的岛屿
        System.out.println("\n--- 测试8: 对角线不相连的岛屿 ---");
        testDiagonalIslands(solution);

        // 测试9：长条形岛屿（水平）
        System.out.println("\n--- 测试9: 水平长条岛屿 ---");
        testHorizontalStrip(solution);

        // 测试10：长条形岛屿（垂直）
        System.out.println("\n--- 测试10: 垂直长条岛屿 ---");
        testVerticalStrip(solution);

        // 测试11：环形岛屿
        System.out.println("\n--- 测试11: 环形岛屿 ---");
        testRingShapeIsland(solution);

        // 测试12：大型网格
        System.out.println("\n--- 测试12: 大型网格 ---");
        testLargeGrid(solution);

        System.out.println("\n=== 所有测试完成 ===");
    }

    /**
     * .测试1：十字形岛屿 + 单独小岛
     * .网格：
     * .  0 1 0 0
     * .  1 1 1 0
     * .  0 1 0 0
     * .  0 0 0 1
     * .岛屿1：十字形，面积=5
     * .岛屿2：单独小岛，面积=1
     * .最大面积=5
     */
    private static void testCrossShapeIsland(S80_Mid_695_岛屿的最大面积 solution) {
        int[][] grid = {
                {0, 1, 0, 0},
                {1, 1, 1, 0},
                {0, 1, 0, 0},
                {0, 0, 0, 1}
        };
        System.out.println("创建网格:");
        printGrid(grid);
        int result = solution.maxAreaOfIsland(deepCopy(grid));
        System.out.println("maxAreaOfIsland() -> " + result + " (期望: 5)");
        assert result == 5 : "测试1失败，期望值为5";
        System.out.println("✓ 十字形岛屿测试通过");
    }

    /**
     * .测试2：全为海洋
     * .网格：
     * .  0 0 0
     * .  0 0 0
     * .  0 0 0
     * .最大面积=0
     */
    private static void testAllWater(S80_Mid_695_岛屿的最大面积 solution) {
        int[][] grid = {
                {0, 0, 0},
                {0, 0, 0},
                {0, 0, 0}
        };
        System.out.println("创建网格: 全为海洋 (3x3)");
        printGrid(grid);
        int result = solution.maxAreaOfIsland(deepCopy(grid));
        System.out.println("maxAreaOfIsland() -> " + result + " (期望: 0)");
        assert result == 0 : "测试2失败，期望值为0";
        System.out.println("✓ 全为海洋测试通过");
    }

    /**
     * .测试3：全为陆地
     * .网格：
     * .  1 1 1
     * .  1 1 1
     * .  1 1 1
     * .最大面积=9
     */
    private static void testAllLand(S80_Mid_695_岛屿的最大面积 solution) {
        int[][] grid = {
                {1, 1, 1},
                {1, 1, 1},
                {1, 1, 1}
        };
        System.out.println("创建网格: 全为陆地 (3x3)");
        printGrid(grid);
        int result = solution.maxAreaOfIsland(deepCopy(grid));
        System.out.println("maxAreaOfIsland() -> " + result + " (期望: 9)");
        assert result == 9 : "测试3失败，期望值为9";
        System.out.println("✓ 全为陆地测试通过");
    }

    /**
     * .测试4：多个独立小岛
     * .网格：
     * .  1 0 0 1
     * .  1 0 0 1
     * .  0 0 0 0
     * .  1 1 0 0
     * .岛屿1：左上角，面积=2
     * .岛屿2：右上角，面积=2
     * .岛屿3：左下角，面积=2
     * .最大面积=2
     */
    private static void testMultipleIslands(S80_Mid_695_岛屿的最大面积 solution) {
        int[][] grid = {
                {1, 0, 0, 1},
                {1, 0, 0, 1},
                {0, 0, 0, 0},
                {1, 1, 0, 0}
        };
        System.out.println("创建网格: 多个独立小岛");
        printGrid(grid);
        int result = solution.maxAreaOfIsland(deepCopy(grid));
        System.out.println("maxAreaOfIsland() -> " + result + " (期望: 2)");
        assert result == 2 : "测试4失败，期望值为2";
        System.out.println("✓ 多个独立小岛测试通过");
    }

    /**
     * .测试5：LeetCode 官方示例 1
     * .较大的网格，最大岛屿面积=6
     */
    private static void testLeetCodeExample1(S80_Mid_695_岛屿的最大面积 solution) {
        int[][] grid = {
                {0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0},
                {0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0},
                {0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0},
                {0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0}
        };
        System.out.println("创建网格: LeetCode 官方示例 (8x13)");
        System.out.println("(网格较大，略过打印)");
        int result = solution.maxAreaOfIsland(deepCopy(grid));
        System.out.println("maxAreaOfIsland() -> " + result + " (期望: 6)");
        assert result == 6 : "测试5失败，期望值为6";
        System.out.println("✓ LeetCode 官方示例测试通过");
    }

    /**
     * .测试6：单个陆地格子
     * .网格：
     * .  0 0 0
     * .  0 1 0
     * .  0 0 0
     * .最大面积=1
     */
    private static void testSingleLand(S80_Mid_695_岛屿的最大面积 solution) {
        int[][] grid = {
                {0, 0, 0},
                {0, 1, 0},
                {0, 0, 0}
        };
        System.out.println("创建网格: 单个陆地格子");
        printGrid(grid);
        int result = solution.maxAreaOfIsland(deepCopy(grid));
        System.out.println("maxAreaOfIsland() -> " + result + " (期望: 1)");
        assert result == 1 : "测试6失败，期望值为1";
        System.out.println("✓ 单个陆地格子测试通过");
    }

    /**
     * .测试7：L形岛屿
     * .网格：
     * .  1 0 0
     * .  1 0 0
     * .  1 1 1
     * .最大面积=5
     */
    private static void testLShapeIsland(S80_Mid_695_岛屿的最大面积 solution) {
        int[][] grid = {
                {1, 0, 0},
                {1, 0, 0},
                {1, 1, 1}
        };
        System.out.println("创建网格: L形岛屿");
        printGrid(grid);
        int result = solution.maxAreaOfIsland(deepCopy(grid));
        System.out.println("maxAreaOfIsland() -> " + result + " (期望: 5)");
        assert result == 5 : "测试7失败，期望值为5";
        System.out.println("✓ L形岛屿测试通过");
    }

    /**
     * .测试8：对角线不相连的岛屿
     * .网格：
     * .  1 0 0
     * .  0 1 0
     * .  0 0 1
     * .对角线不算相邻，每个都是单独的岛屿
     * .最大面积=1
     */
    private static void testDiagonalIslands(S80_Mid_695_岛屿的最大面积 solution) {
        int[][] grid = {
                {1, 0, 0},
                {0, 1, 0},
                {0, 0, 1}
        };
        System.out.println("创建网格: 对角线不相连的岛屿");
        printGrid(grid);
        int result = solution.maxAreaOfIsland(deepCopy(grid));
        System.out.println("maxAreaOfIsland() -> " + result + " (期望: 1)");
        assert result == 1 : "测试8失败，期望值为1";
        System.out.println("✓ 对角线不相连测试通过");
    }

    /**
     * .测试9：水平长条岛屿
     * .网格：
     * .  0 0 0 0 0
     * .  1 1 1 1 1
     * .  0 0 0 0 0
     * .最大面积=5
     */
    private static void testHorizontalStrip(S80_Mid_695_岛屿的最大面积 solution) {
        int[][] grid = {
                {0, 0, 0, 0, 0},
                {1, 1, 1, 1, 1},
                {0, 0, 0, 0, 0}
        };
        System.out.println("创建网格: 水平长条岛屿");
        printGrid(grid);
        int result = solution.maxAreaOfIsland(deepCopy(grid));
        System.out.println("maxAreaOfIsland() -> " + result + " (期望: 5)");
        assert result == 5 : "测试9失败，期望值为5";
        System.out.println("✓ 水平长条岛屿测试通过");
    }

    /**
     * .测试10：垂直长条岛屿
     * .网格：
     * .  0 1 0
     * .  0 1 0
     * .  0 1 0
     * .  0 1 0
     * .最大面积=4
     */
    private static void testVerticalStrip(S80_Mid_695_岛屿的最大面积 solution) {
        int[][] grid = {
                {0, 1, 0},
                {0, 1, 0},
                {0, 1, 0},
                {0, 1, 0}
        };
        System.out.println("创建网格: 垂直长条岛屿");
        printGrid(grid);
        int result = solution.maxAreaOfIsland(deepCopy(grid));
        System.out.println("maxAreaOfIsland() -> " + result + " (期望: 4)");
        assert result == 4 : "测试10失败，期望值为4";
        System.out.println("✓ 垂直长条岛屿测试通过");
    }

    /**
     * .测试11：环形岛屿（中间是海洋）
     * .网格：
     * .  1 1 1 1
     * .  1 0 0 1
     * .  1 0 0 1
     * .  1 1 1 1
     * .最大面积=12
     */
    private static void testRingShapeIsland(S80_Mid_695_岛屿的最大面积 solution) {
        int[][] grid = {
                {1, 1, 1, 1},
                {1, 0, 0, 1},
                {1, 0, 0, 1},
                {1, 1, 1, 1}
        };
        System.out.println("创建网格: 环形岛屿");
        printGrid(grid);
        int result = solution.maxAreaOfIsland(deepCopy(grid));
        System.out.println("maxAreaOfIsland() -> " + result + " (期望: 12)");
        assert result == 12 : "测试11失败，期望值为12";
        System.out.println("✓ 环形岛屿测试通过");
    }

    /**
     * .测试12：大型网格（10x10）
     * .测试较大规模的场景
     */
    private static void testLargeGrid(S80_Mid_695_岛屿的最大面积 solution) {
        int[][] grid = new int[10][10];
        // 创建一个大岛屿（左上半部分）
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                grid[i][j] = 1;
            }
        }
        // 添加一个小岛屿（右下角）
        grid[8][8] = 1;
        grid[8][9] = 1;
        grid[9][8] = 1;
        grid[9][9] = 1;

        System.out.println("创建网格: 大型网格 (10x10)");
        System.out.println("(网格较大，略过打印)");
        int result = solution.maxAreaOfIsland(deepCopy(grid));
        System.out.println("maxAreaOfIsland() -> " + result + " (期望: 25)");
        assert result == 25 : "测试12失败，期望值为25";
        System.out.println("✓ 大型网格测试通过");
    }

    /**
     * .工具方法：打印网格（便于观察）
     */
    private static void printGrid(int[][] grid) {
        for (int[] row : grid) {
            System.out.print("  ");
            for (int cell : row) {
                System.out.print(cell + " ");
            }
            System.out.println();
        }
    }

    /**
     * .工具方法：对矩阵做深拷贝，避免在测试里被原地修改
     */
    private static int[][] deepCopy(int[][] grid) {
        if (grid == null) return null;
        int[][] copy = new int[grid.length][];
        for (int i = 0; i < grid.length; i++) {
            copy[i] = new int[grid[0].length];
            System.arraycopy(grid[i], 0, copy[i], 0, grid[0].length);
        }
        return copy;
    }
}
